package com.mlh.binarytree;

/**
 * @author 缪林辉
 * @date 2024/3/29 11:18
 * @DESCRIPTION
 */
//给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

public class 验证二叉搜索树 {

    public static void main(String[] args) {
        System.out.println(Integer.MAX_VALUE);
    }
    public boolean method1(TreeNode root) {
        int[] res = recursion(root);
        return res[0]==1;
    }
    // int[0] 该树是否为二叉排序树
    // int[1] 该树的最小值
    // int[2] 该树的最大值
    public int[] recursion(TreeNode node){
        if (node == null) {
            //因为那后面的一连串的if,导致这里没多大意义，就是为了能够返回正确的格式，正常递归
            //如果没有一连串if就有意义了
            return new int[]{1,Integer.MIN_VALUE, Integer.MAX_VALUE};
        }
        int[]res=new int[3];
        int[]left = recursion(node.left);
        int[]right = recursion(node.right);
        boolean b1=left[0]+right[0]==2;
        boolean b2;
        //这一步就是防止题目恶心，[-2147483648] [-2147483648,-2147483648] [2147483647,null,-2147483648] 搞这种东西
        if(node.left==null&&node.right!=null){
            b2=node.val<right[1];
        }else if (node.left!=null&&node.right==null){
            b2=node.val>left[2];
        }else if(node.left==null&&node.right==null){
            b2=true;
        }else{
            b2=node.val>left[2]&&node.val<right[1];
        }
        res[0]=b1&&b2?1:0;
        //寻找该子树节点的最大值和最小值
        res[1]=Math.min(node.val,Math.min(left[1],right[1]));
        res[2]=Math.max(node.val,Math.max(left[2],right[2]));
        return res;
    }
    //上面那个方法是由下到上的  左右子树提供最大值和最小值信息
    //而这个方法则是有上到下的  给子树提供上一个节点的上界和下界
    public boolean method2(TreeNode root) {
        return recursion2(root,Long.MAX_VALUE,Long.MIN_VALUE);
    }

    private boolean recursion2(TreeNode root, long min, long max) {
        if(root==null){
            return true;
        }
        if(root.val>=min||root.val<=max){//带等于号 须严格递增
            return false;
        }
        return recursion2(root.left,root.val,max)&&recursion2(root.right,min,root.val);
    }

    public boolean practice(TreeNode root) {
        return recursionPractice(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    //判断以该节点为根节点的树是否为平衡排序树
    private boolean recursionPractice(TreeNode node, long min, long max) {
        if(node==null){
            return true;
        }
        if(node.val<=min||node.val>=max){
            return false;
        }
        return recursionPractice(node.left,min,node.val)&&recursionPractice(node.right,node.val,max);
    }
}
